#pragma once

#include <limits>
#include <boost/circular_buffer.hpp>

#include "sdeque.h"
#include "wsdeque.h"
#include "../utils/misc.h"

namespace mdtx::online::container
{
    template <typename T>
    class sorted_robuf
    {
    public:
        boost::circular_buffer<T> buf;
        sdeque<T> sorted{};

        explicit sorted_robuf(ptrdiff_t period)
            : buf(period)
        {
        }

        bool full()
        {
            return buf.full();
        }

        void insert(T x)
        {
            if (buf.full())
            {
                sorted.erase(buf.front());
            }
            sorted.insert(x);
            buf.push_back(x);
        }
    };

    template <typename T, typename U>
    class wsorted_robuf
    {
    public:
        using datum_type = wsnode<T, U>;

        boost::circular_buffer<datum_type> buf;
        wsdeque<T, U> sorted{};

        explicit wsorted_robuf(ptrdiff_t period)
            : buf(period)
        {
        }

        bool full()
        {
            return buf.full();
        }

        void insert(T x, U w)
        {
            if (buf.full())
            {
                sorted.erase(buf.front());
            }
            sorted.insert(datum_type{x, w});
            buf.push_back(datum_type{x, w});
        }
    };

    template <typename T, size_t N>
    class quantile_robuf : public sorted_robuf<T>
    {
        using base = sorted_robuf<T>;

        std::array<ptrdiff_t, N> qidx;
        std::array<T, N> qlin;

    public:
        quantile_robuf(ptrdiff_t period, const std::array<T, N> &u)
            : base(period)
        {
            for (size_t i = 0; i < N; ++i)
            {
                if (u[i] > 1)
                {
                    qidx[i] = period - 1;
                    qlin[i] = 0;
                }
                else
                {
                    T tmp = (period - 1) * u[i];
                    qidx[i] = static_cast<ptrdiff_t>(tmp);
                    qlin[i] = tmp - qidx[i];
                }
            }
        }

        auto get() const
        {
            std::array<T, N> q{};
            if (this->buf.full())
            {
                for (size_t i = 0; i < N; ++i)
                {
                    if (qlin[i] == 0)
                    {
                        q[i] = this->sorted[qidx[i]];
                    }
                    else
                    {
                        q[i] = this->sorted[qidx[i]] + (this->sorted[qidx[i] + 1] - this->sorted[qidx[i]]) * qlin[i];
                    }
                }
            }
            return q;
        }
    };

    template <typename T>
    class ranked_robuf
    {
    public:
        boost::circular_buffer<T> buf;
        boost::circular_buffer<ptrdiff_t> rank;
        sdeque<T> sorted{};

        explicit ranked_robuf(ptrdiff_t period)
            : buf(period), rank(period)
        {
        }

        bool full()
        {
            return buf.full();
        }

        void insert(T x)
        {
            ptrdiff_t pop = std::numeric_limits<ptrdiff_t>::max();
            if (buf.full())
            {
                sorted.erase(buf.front());
                pop = rank.front();
            }
            buf.push_back(x);

            auto it = sorted.insert(x);
            ptrdiff_t push = std::distance(sorted.begin(), it);
            for (auto &i : rank)
            {
                if (i > pop)
                {
                    i -= 1;
                }
                if (i >= push)
                {
                    i += 1;
                }
            }
            rank.push_back(push);
        }
    };
}
